//题目:
// 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
// 整数除法仅保留整数部分。
// 你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
// 注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

#include<iostream>
#include<stack>

using namespace std;
//代码：
class Solution 
{
public:
    int calculate(string s) 
    {
        //法一：
        // int ret=0;
        // stack<int> st;
        // char opr='+';
        // vector<string> v_str;//将s中的整数提取出来
        // for(int i=0;i<s.size();i++)
        // {
        //     if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')v_str.push_back(string(1,s[i]));
        //     else if(s[i]>='0' && s[i]<='9')
        //     {
        //         int left=i,right=i;
        //         while(right<s.size() && s[right]>='0' && s[right]<='9')right++;
        //         v_str.push_back(string(s.begin()+left,s.begin()+right));//[left,right)
        //         i=right-1;
        //     }
        // }
        // for(auto& str:v_str)cout<<str<<" ";
        // for(int i=0;i<v_str.size();i++)
        // {   
        //     //先算乘除、后算加减、符号代入
        //     if(v_str[i]=="+")opr='+';
        //     else if(v_str[i]=="-")opr='-';
        //     else if(v_str[i]=="*")opr='*';
        //     else if(v_str[i]=="/")opr='/';
        //     else
        //     {
        //         if(opr=='-')
        //             st.push(-1*stoi(v_str[i].c_str()));
        //         else if(opr=='*')
        //         {
        //             int left=st.top();
        //             st.pop();
        //             int right=stoi(v_str[i].c_str());
        //             st.push(left*right);
        //         }
        //         else if(opr=='/')
        //         {
        //             int left=st.top();
        //             st.pop();
        //             int right=stoi(v_str[i].c_str());
        //             st.push(left/right);
        //         }
        //         else st.push(stoi(v_str[i].c_str()));
        //     }
        // }
        // while(!st.empty())
        // {
        //     ret+=st.top();
        //     st.pop();
        // }
        // return ret;

        //法二：
        stack<int> st;
        int ret=0;
        char opr='+';
        for(int i=0;i<s.size();i++)
        {
            //遇到操作符，就更新
            if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')opr=s[i];
            //遇到非操作符
            else if(s[i]>='0' && s[i]<='9')
            {
                //1.先将数字提取出来
                long num=0,flag=0;
                while(i<s.size() && s[i]>='0' && s[i]<='9'){
                    if(flag)
                        num=num*10+s[i]-'0';
                    else 
                        num+=s[i]-'0',flag=1;
                    i++;
                }
                //2.更新i的值,因为i下一步还要++
                i-=1;
                //3.根据opr将num入栈
                if(opr=='+')st.push(num);
                if(opr=='-')
                    st.push(-1*num);
                if(opr=='*')
                {
                    int left=st.top();
                    st.pop();
                    st.push(left*num);
                }
                if(opr=='/')
                {
                    int left=st.top();
                    st.pop();
                    st.push(left/num);
                }
            }
        }
        while(!st.empty())ret+=st.top(),st.pop();
        return ret;
    }
};